public class MaxProfit {
    // leetcode 买卖股票的最佳时机
    // https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-100-liked

    /**
     * 贪心，通过两个变量min、max来维护已经遍历的元素中最小和最大的元素
     * 然后通过ret变量来记录最终的结果
     * 当遇到大于max的元素的时候，就更新max以及ret的值
     * 当遇到小于min的元素的时候，就更新min和max的值，这里为什么需要更新max的值，因为股票必须是先买再卖，贪心就是价格最低的时候买入
     * 价格最高的时候卖出,遇到小于min元素的时候也更新max的值就可以保证max在min之后
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int min = prices[0], max = prices[0], ret = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > max) {
                max = prices[i];
                ret = Math.max(ret, max - min);
            }else if (prices[i] < min) {
                min = max = prices[i];
            }
        }
        return ret;
    }

    /**
     * dp
     * @param prices
     * @return
     */
    public int maxProfit1(int[] prices) {
        int len = prices.length;
        // 对于同一天有两种状态：买入状态（手上有股票，但是不一定是当天买入的），卖出状态（手上没有股票，不一定是当天卖出的）
        // dp[i][0]表示当天不买也不卖的最大利润
        // dp[i][1]表示当天卖出股票的最大利润
        int[][] dp = new int[len][2];
        dp[0][0] = -prices[0];
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
        }
        return dp[len-1][1];
    }

    /**
     * dp优化
     * @param prices
     * @return
     */
    public int maxProfit2(int[] prices) {
        int len = prices.length;
        // 对于同一天有两种状态：买入状态（手上有股票，但是不一定是当天买入的），卖出状态（手上没有股票，不一定是当天卖出的）
        // dp[i][0]表示当天不买也不卖的最大利润
        // dp[i][1]表示当天卖出股票的最大利润
        int[] dp = new int[2];
        dp[0] = -prices[0];
        for (int i = 1; i < len; i++) {
            dp[0] = Math.max(dp[0], -prices[i]);
            dp[1] = Math.max(dp[1], dp[0] + prices[i]);
        }
        return dp[1];
    }
}
